#include <stdio.h>

void Bulle(int *a,int size)
{
    for(int i = 0;i < size -1;i++)
    {
        int flag = 0;
        for(int j = 0;j < size-1;j++)
        {
            if(a[j] > a[j+1])
            {
                int temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
                flag = 1;
            }
        }
        if(flag == 0)
            break;
    }
    
}

void Insert(int *a,int size)
{
    for(int i = 1;i < size;i++)
    {
        int j = i;
        int temp = a[j];
        for(;j > 0;j--)
        {
            if(a[j-1] > temp)
                a[j] = a[j-1];
            else
                break;
        }
        a[j] = temp;
    }
}

void Choose(int *a,int size)
{
    for(int i = 0;i < size ;i++)
    {
        int min = i;
        int temp = a[min];
        for(int j = i + 1;j < size;j++)
        {
            if(a[j] < temp)
                min = j;
        }
        a[i] = a[min];
        a[min] = temp;
    }
}

void Swep(int *a,int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

void Choose2(int*a,int size)
{
    int left = 0;
    int right = size - 1;
    while(left < right)
    {
        int min = left;
        int max = right;
        for(int j = left;j <= right;j++)
        {
            if(a[min] > a[j])
                min = j;
            if(a[max] < a[j])
                max = j;
        }
        Swep(&a[min],&a[left]);
        if(max == left)
        {
            max == min;
        }
        Swep(&a[max],&a[right]);
        left++;
        right--;
    }
}

void Fast(int *a,int start,int end)
{
    if(start >= end)
        return;
    int left = start;
    int right = end;
    int temp = a[start];
    while(left < right)
    {
        while(a[right] > temp && left < right)
            right--;
        if(left < right)
            a[left++] = a[right];
        while(a[left] < temp && left < right)
            left++;
        if(left < right)
            a[right--] = a[left];
    }
    a[left] = temp;
    Fast(a,start,left-1);
    Fast(a,right+1,end);
}

int Er(int *a,int size,int n)
{
    int left = 0;
    int right = size - 1;
    while(left <= right)
    {
        int mid = left + (right - left)/2;
        if(a[mid] > n)
        {
            right = mid - 1;
        }
        else if(a[mid] < n)
        {
            left = mid + 1;
        }
        else if(a[mid] == n)
        {
            return mid;
        }
    }
    return -1;
}

int main()
{
    int a[] = {3,9,11,5,27,1};
    int size = sizeof(a)/sizeof(a[0]);
    //Bulle(a,size);
    //Insert(a,size);
    //Choose(a,size);
    //Choose2(a,size);
    Fast(a,0,size-1);

   int n = Er(a,size,5);
    for(int i = 0;i < size;i++)
        printf("%d ",a[i]);
    printf("\n");
    printf("%d\n",n);
    return 0;
}